package demo2;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: DELL
 * Date: 2023-09-04
 * Time: 7:16
 */

import java.util.Arrays;

/**
 * 快速排序思想 : 寻找一个基准元素, 将排序数据以该基准元素划分, 重复上述操作, 当每次划分后的数组在重新
 * 根据基准元素进行划分, 逐渐分治成一个只有一个元素的数组时就有序了. 最终达到整个排序数组有序
 * <p>
 *              TODO : 为什么寻找基准的方法中, 都是先寻找右边在寻找左边 ?
 *                     原因在于如果先寻找左边, 那么会先和初始以 left 位置为基准元素的位置位置交换
 *                     让大于基准元素的数交换到进来寻找基准元素数组的最左边去了, 最终导致寻找基准结束后
 *                     出现一个大于基准的数在最左边, 没有完全让大于基准的数都在基准右边
 */
public class QuickSort {

    /**
     * 基础版本的快快排
     * TODO : 时间复杂度分析, 排序数组分治后的数组高度为 logN, 每层有 N 个元素要进行排序 O(N*logN)
     *        空间复杂度分析, 先进行递归左边的数组, 会不断地向下分治, 直到数组为元素个数为 1 才结束
     *                     而分治的数字类似单分支二叉树, 高度决定了分治的数组的个数 O(logN).
     *                     当递归右边时, 左边肯定已经排序结束回收. 最终为 O(logN)
     *        稳定性分析, 不稳定排序
     *        快排时间复杂度较低, 性能也比较优
     */
//    public static void quickSort(int[] array, int start, int end) {
//        // 只有一个元素, 无需在划分结束递归, 此时该分治数组已经有序
//        if (start >= end) {
//            return;
//        }
//
//        // 1. 根据基准元素划分数组进行分治
//        int pivot = partitionDigHole(array, start, end);
//
//        // 2. 递归基准元素左边
//        quickSort(array, 0, pivot - 1);
//        // 3. 递归基准元素右边
//        quickSort(array, pivot + 1, end);
//    }


    /**
     * 快排增强版 - 1. 使用三数取中法   2. 分治数组长度为一定长度时(例如 7 个元素以内)
     * 三数取中法 : 优化[1,2,3] 这种情况, 如果以左边界 1 为基准元素, 那么会划分成类似单分支树, 导致效率下降
     * 因此需要提前的进行合理的传入初始基准元素, 让分治的数组更加均匀.
     * <p>
     * 分治长度一定时, 采取插入排序 : 当分治到数组长度一定程度以内时, 由于不断地分治, 已经趋近于有序, 此时直接插入排序,
     * 直接插入排序在越有序时越快,不在进行分治去排序, 提高快排效率
     */
    public static void quickSort(int[] array, int start, int end) {
        // 只有一个元素, 无需在划分结束递归, 此时该分治数组已经有序
        // TODO : 当给定需要排序的数组为 1 2 3 4 5 时, 此时找到基准 pivot 在 0 位置, 然后递归其左边, 结束位置 end 为 pivot - 1
        //        此时如果没有 > 条件限制, 会继续向下排序, 导致越界
        if (start >= end) {
            return;
        }

        // TODO : 优化二, 小数组已经趋近于有序, 采用直接插入排序更快
        //        同时还需要注意, 这里 start 和 end 都是下标, 元素的话需要 + 1
        if (end - start + 1 <= 6) {
            insertSort(array, start, end);
        }

        // TODO : 优化一, 提前寻找需要排序数组的基准元素
        int index = findMidOfThreeNum(array, start, end);

        // TODO : 然后交换到当前排序数组的左边界上, 供下次进行寻找基准元素时以左边界为基准开始
        swap(array, index, start);

        // 1. 根据基准元素划分数组进行分治
        int pivot = partitionDigHole(array, start, end);

        // 2. 递归基准元素左边
        quickSort(array, 0, pivot - 1);
        // 3. 递归基准元素右边
        quickSort(array, pivot + 1, end);
    }


    /**
     * 插入排序思想 : 从左往右每个元素 i 都作为一次插入的数, 首次从第二个数开始, 以 i 前面的有序数组做比较
     * 然后决定插入到 i 前面的有序数组中的那个位置, 最终所有元素插入成功
     */
    private static void insertSort(int[] array, int left, int right) {
        // TODO : 这里传入得都是下标, 要注意下标和元素位置关系
        for (int i = left + 1; i <= right; i++) {
            int tmp = array[i];
            int j = i - 1;
            for (; j >= left; j--) {
                if (array[j] > tmp) {
                    array[j + 1] = array[j];
                } else {
                    break;
                }
            }
            array[j + 1] = tmp;
        }
    }


    public static int findMidOfThreeNum(int[] array, int start, int end) {
        //  寻找中间元素下标, 防止排序的数组太长, 直接相加除 2 容易越界
        int midIndex = start + ((end - start) >> 2);

        // 头比尾小 3    X    9
        if (array[start] < array[end]) {
            // 此时如果中间元素 X 大于 end 位置元素, 那么 end 元素就是中间值
            if (array[midIndex] > array[end]) {
                return end;
            } else if (array[midIndex] < array[start]) {
                // 此时中间元素 X 比 start 位置元素小, 那么 start 就是中间值
                return start;
            } else {
                return midIndex;
            }

        } else {
            // 9    X    3   or    3     X     3
            if (array[midIndex] > array[start]) {
                return start;
            } else if (array[midIndex] < array[end]) {
                return end;
            } else {

                return midIndex;
            }
        }
    }


    /**
     * hoare 法寻找基准元素 : 类似双指针思想, 以传入数组左边界位置的值为基准, 从两端向中间寻找
     * 右边寻找小于基准的, 左边寻找比基准大的, 然后进行交换, 一直到两指针相遇结束
     * 最终, 将基准元素放到指针相遇处, 将该数组够造成左边都小于基准, 右边都大于基准
     *
     * @param array 需要划分得数组
     * @param left  划分数组的左边界
     * @param right 划分数组的右边界
     * @return 返回新的基准元素下标位置
     */
    private static int partitionHoare(int[] array, int left, int right) {
        // 以每次划分的数组的左边第一个元素为基准下标
        int i = left;
        // 记录基准下标位置对应元素值
        int pivot = array[left];
        // 从两端向中间寻找, 左边找大于 pivot 的数, 右边找小于 prvot 的数
        while (left < right) {
            // 1. 先在右边寻找比基准小的数
            while (left < right && array[right] >= pivot) {
                right--;
            }

            // 2. 在右边寻找比基准大的数
            while (left < right && array[left] <= pivot) {
                left++;
            }

            // 3. 交换 left 和 right 下标的值
            swap(array, left, right);
        }

        // 此时 left = right, 说明比基准小的和比基准大的都已经划分好了, 并以相遇这个位置为界限
        // 因此需要将基准元素放在此位置, 左边则比这个基准都小, 右边都比基准都大
        swap(array, left, i);

        // 此时相遇的位置就是基准元素最终所在位置, 返回这个基准位置
        return left; // right 也可
    }


    public static int partitionDigHole(int[] array, int left, int right) {
        // 1. 以数组的左边界值为基准坑位元素
        int pivot = array[left];

        while (left < right) {
            // 1. 先从右边寻找比基准元素小的值
            while (left < right && array[right] >= pivot) {
                right--;
            }

            // 2. 将坑位元素变成此时 right 位置元素
            array[left] = array[right];

            // 3. 然后左边寻找比基准元素小的值
            while (left < right && array[left] <= pivot) {
                left++;
            }

            // 4. 将坑位元素 array[right] 更改
            array[right] = array[left];
        }

        // 将初始坑位的值放在当前最后的空位中完成基准元素位置的放置
        array[left] = pivot;

        return left;
    }

    private static void swap(int[] array, int left, int right) {
        int tmp = array[left];
        array[left] = array[right];
        array[right] = tmp;
    }


    public static void main(String[] args) {
        int[] array = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48, 2, 141, 142, 2, 34, 634, 64, 23, 55, 21, 44};
        // 因为是下标, 因此需要 array.length - 1
        QuickSort.quickSort(array, 0, array.length - 1);
        System.out.println(Arrays.toString(array));
    }
}
